#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
struct ListNode
{
    int val;
    struct ListNode* next;
};


//移除链表元素
struct ListNode* removeElements(struct ListNode* head, int val)
{
    if (head == NULL)
        return NULL;
    struct ListNode* current = head;
    struct ListNode* prev = head;

    while (current != NULL)
    {
        if (head->val == val)
        {
            struct ListNode* temp = head;
            head = temp->next;
            free(temp);
            temp = NULL;
            current = head;
        }
        else
        {
            if (current->val == val)
            {
                prev->next = current->next;
                struct ListNode* temp = current;
                current = current->next;
                free(temp);
                temp = NULL;
            }
            else
            {
                prev = current;
                current = current->next;
            }
        }
    }
    return head;
}

 //翻转链表
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;
    if (head == NULL)
        return NULL;
    else
    {
        while (n2 != NULL)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3 != NULL)
            {
                n3 = n3->next;
            }
        }
        return n1;
    }
}

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
        while (n2 != NULL)
        {
            struct ListNode* n3 = n2->next;
            //头插
            n2->next = n1;
            n1 = n2;

            //迭代
            n2 = n3;
        }
        return n1;
}


void SListPrint(struct ListNode* plist)
{
    struct ListNode* current = plist;
    while (current != NULL)
    {
        printf("%d->", current->val);
        current = current->next;
    }
    printf("NULL\n");
}

int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    n1->val = 1;
    n2->val = 2;
    n3->val = 3;
    n4->val = 4;
    n5->val = 5;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = NULL;
    SListPrint(n1);
    n1 = reverseList(n1);
    SListPrint(n1);

    return 0;
}

//链表的中间结点

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;

}


 //链表中倒数第k个结点

//第一种
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
    // write code here
    if (k == 0)
        return NULL;
    if (pListHead == NULL)
        return NULL;
    struct ListNode* current = pListHead;
    struct ListNode* rem = pListHead;
    while (current != NULL)
    {
        if (current != pListHead)
        {
            current = rem->next;
        }
        rem = current;
        int temp = k;
        while (temp--)
        {
            if (current == NULL)
            {
                return NULL;
            }
            current = current->next;
        }
    }
    return rem;
}

//第二种(效率更高)
 //只遍历了一次：第一步，改变fast和slow的距离为k；第二步，同时移动fast和slow，直到fast为NULL


struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
    // write code here
    if (k == 0)
        return NULL;
    //下面已经有判断机制了
    //if (pListHead == NULL)
    //    return NULL;
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    int temp = k;
    while (temp--)
    {
        if (fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    while (fast != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}






 //合并两个有序链表

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL && list2 != NULL)
        return list2;
    else if (list1 != NULL && list2 == NULL)
        return list1;
    struct ListNode* head = NULL, * tail = NULL;
    while (list1 && list2)
    {
        if (list1->val > list2->val)
        {
            if (head == NULL)
            {
                tail = head = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;

        }
        else
        {
            if (head == NULL)
            {
                tail = head = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
    }
    while (list1 != NULL)
    {
        tail->next = list1;
        tail = tail->next;
        list1 = list1->next;
    }
    while (list2 != NULL)
    {
        tail->next = list2;
        tail = tail->next;
        list2 = list2->next;
    }
    return head;
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL && list2 != NULL)
        return list2;
    else if (list1 != NULL && list2 == NULL)
        return list1;
    struct ListNode* head = NULL, * tail = NULL;
    if (list1->val > list2->val)//这里做了一点点优化
    {
        tail = head = list2;
        list2 = list2->next;
    }
    else
    {
        tail = head = list1;
        list1 = list1->next;
    }
    while (list1 && list2)
    {
        if (list1->val > list2->val)
        {

            tail->next = list2;
            tail = tail->next;

            list2 = list2->next;

        }
        else
        {

            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
    }
    while (list1 != NULL)
    {
        tail->next = list1;
        tail = tail->next;
        list1 = list1->next;
    }
    while (list2 != NULL)
    {
        tail->next = list2;
        tail = tail->next;
        list2 = list2->next;
    }
    return head;
}

 //带哨兵位的头节点，这样就不需要判断头节点是否为空了，返回值是head->next，但是要释放哨兵位节点的空间

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL && list2 != NULL)
        return list2;
    else if (list1 != NULL && list2 == NULL)
        return list1;
    struct ListNode* head = NULL,  * tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (list1 && list2)
    {
        if (list1->val > list2->val)
        {

            tail->next = list2;
            tail = tail->next;

            list2 = list2->next;

        }
        else
        {

            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
    }
    while (list1 != NULL)
    {
        tail->next = list1;
        tail = tail->next;
        list1 = list1->next;
    }
    while (list2 != NULL)
    {
        tail->next = list2;
        tail = tail->next;
        list2 = list2->next;
    }
    //防止内存泄漏
    struct ListNode* temp = head;
    free(temp);
    temp = NULL;
    return head->next;
}

